El m\'etodo de direcciones conjugadas se aplica para resolver sistemas 
de la forma $Ax = b$ en aquellos casos en los que la matriz $A$ es 
\textbf{sim\'etrica definida positiva}.
Es un m\'etodo iterativo que se aproxima a la soluci\'on $x^*$ del 
sistema movi\'endose sobre direcciones A-conjugadas.

Se convierte el problema en uno de optimizaci\'on, que es hallar el 
m\'inimo de una funci\'on $Q(x)$. 
Esta funci\'on se elige especialmente para que sus m\'inimos coincidan 
con las soluciones de $Ax = b$.
$$ Q(x) = \frac{1}{2}x^{t}Ax - b^t x$$

\begin{theorem}
	El gradiente de $Q(x)$, $\nabla Q(x) = Ax-b$ vale cero cuando 
	$Ax = b$. 
	Es posible afirmar que todos los puntos cr\'iticos son m\'inimos 
	pues al derivar nuevamente el gradiente se obtiene $A$ y como $A$ 
	es definida positiva todo punto cr\'itico de $Q(x)$ es un m\'inimo.
\end{theorem}

\begin{figure}[H] \centering
	\subfloat{\includegraphics[scale=.60]{images/gcr2canonicos.pdf}}
	\caption{Paraboloide y curvas de nivel en $\real^2$. 
			Minimizaciones siguiendo los vectores can\'onicos.}	
\end{figure}

Un esquema para los algoritmos de optimizaci\'on es una sucesi\'on 
$x_{k+1}=x_{k}+\alpha_{k}d_{k}$ que tiende a la soluci\'on, siendo 
$d_{k}$ la direcci\'on en la que avanza el m\'etodo y $\alpha_{k}$ 
cu\'anto avanza. 
Se debe determinar c\'omo elegirlos.

Calculando $Q(x+\alpha d)$ se obtiene una expresi\'on en funci\'on de 
los factores. Derivando $Q(x)$ en funci\'on de $\alpha$, se puede 
despejar $\alpha$ en funci\'on de $d$. 
%~ Existe un valor $d$ posible para que el movimiento resulte positivo.
$$\alpha=\frac{d^{t}(b-Ax)}{d^{t}Ad}$$

\begin{example}
	En el caso de $\real^{2}$, como puede verse en la figura, la 
	funci\'on obtenida es un paraboloide, las curvas de nivel son 
	elipses con centro en el origen donde se alcanza el m\'inimo.
	Si $A$ es diagonal, los ejes de los elipses est\'an alineados con 
	los ejes de coordenadas, con lo que tomando los vectores can\'onicos
	como direcciones, en cada iteraci\'on se obtiene la coordenada en 
	ese eje de la soluci\'on final. 
	En cada iteraci\'on, el algoritmo se acerca a la soluci\'on en esa 
	direcci\'on. Por lo tanto, en $2$ iteraciones el m\'etodo converge.
\end{example}

Sin embargo, como sucede en la mayor\'ia de los casos, $A$ no es 
diagonal y los ejes de las elipses no coinciden con los vectores 
can\'onicos $e_{i}$. 
Por lo tanto, utilizarlos como direcciones de movimiento puede llevar 
a que el m\'etodo requiera m\'as iteraciones para converger, o que no 
converja. 
Se buscan entonces otras direcciones m\'as adecuadas, que ser\'an las 
direcciones $A$-conjugadas.

\begin{definition}
	Sean $A \in \real^{n\times n}$ definida positiva. Los vectores 
	$\{d_{1},\dots,d_{n}\}$ con $d_i \ne 0$ son direcciones 
	\emph{A-conjugadas} si y s\'olo si $d_{i}^{t}Ad_{j}=0$ para todo 
	$i\neq j$.
	Si adem\'as se cumple que $d_{i}^{t}Ad_{i}=1$, son direcciones 
	\emph{A-ortonormales}.
\end{definition}

\begin{definition}
	Se denomina \emph{residuo} del sistema lineal a 
	$\displaystyle r(x) \defas \nabla Q(x) = Ax - b$.
\end{definition}

\begin{theorem}
	Sean $A \in \mathbb{R}^{n\times n}$ sim\'etrica definida positiva 
	y $\{d_1,\dots,d_n\}$ direcciones $A$-conjugadas,
	
	\begin{itemize}	
		\setlength{\itemsep}{0pt}
		\item Las direcciones resultan linealmente independientes.
		\item Si en la sucesi\'on anterior se toman las direcciones 
		A-conjugadas de la matriz $A$, \'esta converge en a lo sumo 
		$n$ pasos.
		\item El residuo de una iteraci\'on es ortogonal a todas las 
		direcciones anteriores, es decir, si $r_{k}=b-Ax_{k}$, entonces 
		$r_{k}^{t}d_{i}=0$ para todo $i \in \{0,\dots,k-1\}$.
	\end{itemize}
\end{theorem}

\begin{theorem}
	Sean $\{d_1,\ldots,d_n\}$ direcciones A-conjugadas y 
	$S = [d_1,\ldots,d_n]$ una matriz que tiene como columnas a las 
	direcciones, entonces se puede definir un nuevo conjunto de 
	variables $\displaystyle \hat{x}=S^{-1}x$, y $\hat{Q}(\hat{x})$ 
	como $$\hat{Q}(\hat{x}) \defas Q(S \hat{x}) = 
	\frac{1}{2}\hat{x}^{t}(S^{t}AS)\hat{x} - (b^{t}S)\hat{x}$$
	De esta forma, $S^{t}AS$ es diagonal y se vuelve al caso anterior, 
	puesto que cada direcci\'on $e_{i}$ en el subespacio generado por 
	$S$ equivale a la direcci\'on $d_{i}$ en el espacio can\'onico.
	Tomando cualquier conjunto de direcciones A-conjugadas se puede 
	aplicar el algoritmo de direcciones conjugadas.
\end{theorem}

\textbf{M\'etodo del gradiente conjugado}
\par
Este m\'etodo es una forma particular de elegir las direcciones 
$A$-conjugadas para luego aplicar el algoritmo anterior. 
Se define el residuo en el paso $k$ como 
$\displaystyle r_{k} \defas r(x_k) = Ax_{k} - b$. 
La direcci\'on en el paso $k$ es elegida como combinaci\'on lineal 
entre la direcci\'on de m\'aximo descenso (el opuesto del gradiente, 
que equivale al opuesto del residuo) y la direcci\'on anterior 
$d_{k-1}$.
$\displaystyle d_k = -r_k + \beta_{k} d_{k-1} $, siendo 
$d_{0}=-r_{0}$.\\

$\beta_k$ se define bajo el requerimiento de que $d_{k-1}$ y $d_k$ sean 
$A$-conjugadas

\begin{displaymath}
	\beta_k = \frac{r_k^t A d_{k-1}}{d_{k-1}^t A d_{k-1}}
\end{displaymath}

Un aspecto interesante de este m\'etodo es que el c\'alculo de cada 
direcci\'on se basa solamente en la anterior, por lo que no es 
necesario mantener en memoria los valores de todas las direcciones 
ya recorridas.

\begin{theorem}
	Las direcciones as\'i generadas verifican que para todo 
	$i \in \{0,\dots,k-1\}$
	\begin{displaymath}
		\begin{array}{rcccl}
		\langle r_{0},\dots,r_{k} \rangle & = 
		& \langle d_{0},\dots,d_{k} \rangle & = 
		& \langle r_{0},Ar_{0},\dots,A^{k}r_{0} \rangle \\
		&& d_{k}^{t}Ad_{i} & = & 0
		\end{array}
	\end{displaymath}
	Es decir, verifican ser $A$-conjugadas, puesto que cada direcci\'on 
	generada es $A$-ortogonal respecto de las anteriores. 
	Tambi\'en se cumple que los residuos son mutuamente ortogonales.
\end{theorem}

\begin{definition} 
	El subespacio $\langle r_{0},Ar_{0},\dots,A^{k}r_{0}\rangle$ se 
	denomina \emph{subespacio de Krylov} de grado $k$ de $r_{0}$.
\end{definition}

\begin{remark}
	Cabe destacar que el nombre Gradiente Conjugado para el m\'etodo es 
	una elecci\'on poco adecuada, puesto que las direcciones utilizadas 
	son $A$-conjugadas y no los gradientes.
\end{remark}

\begin{remark}
	El m\'etodo del gradiente conjugado puede verse como un h\'ibrido 
	entre un algoritmo exacto y un iterativo. 
	Es exacto porque termina como mucho en $n$ pasos, dependiendo de la 
	distribuci\'on de los autovalores de la matriz, y 	es iterativo ya 
	que va generando una sucesi\'on de aproximaciones que convergen a 
	$x^*$ soluci\'on del sistema.
\end{remark}
